package math;

/**
 * Find the next number to the given number which has at least
 * one 3 or 6
 * 
 * Approach:
 * Processing starts from the 1's digit and will move towards most 
 * significant digit handling these cases:
 * 
 * Case 1: Add a number to the 1's digit to turn it into 3 or 6 
 * considering the carry
 * 
 * Case 2: Number has already been increment. Now check only whehter 
 * new number has any other digit, while moving from 1's digit to most
 * significant digit, except 3 or 6. If it's add an appropriate number
 *  to convert it to next 3 or 6 considering the carry. If any digit is 
 *  already 3 or 6, leave it as it is.
 *  
 * Case 3: At the end of step 2, if next num is equal in length to the 
 * given number, it's the answer. If length has increased, answer will be
 * the smallest number of this length with same most significant digit e.g.
 * if given number is 860, number returned from case 2 will be 3363. So the
 * correct answer will be 3000 + 333 = 3333
 * 
 * */
public class FindNextNumber {
	
	/**
	 * flag to check if number has already been incremented.
	 * If yes, only pending item is to check whether remaining digits are
	 * either 3 or 6
	 * 
	 * */
	private static boolean incremented = false;

	public static int findNextNumber(int num){
		
		if(num < 0) throw new IllegalArgumentException("Given number should not be negative!");
		
		int origNum = num;
	
		int digitCount = 1;
		int digit = 0;
		int numAdd = 0;
		
		while(true){ // change the condition
			digit = extractDigit(digitCount, num);

			if(isCompleted(digitCount, num)){
				break;
			}
			
			if(!incremented){
				numAdd = getExtra(digit);
			}else{
				numAdd = confirmValidDigit(digit);
			}
			
			num = num + numAdd * (int)Math.pow(10, digitCount - 1);
			digitCount++;
		}
		
		int origNumLength = findNumberOfDigits(origNum);
		int numLength = findNumberOfDigits(num);
		
		if(numLength > origNumLength){
			num = num / ((int)Math.pow(10, numLength - 1)); // extract the left-most digit
			num = num * (int)Math.pow(10, numLength - 1); // change all other digits to zero

			int extraSum = 0;
			int extraLength = numLength - 1;

			// calculate number consists of only 3's as it's the smallest valid number
			while(extraLength > 0){
				extraSum += 3*(int)Math.pow(10, extraLength - 1);
				extraLength--;
			}
			
			num = num + extraSum;
		}
		
		
		return num;
	}
	
	/**
	 * this method returns a number to be added so that given digit can 
	 * be converted to 3 0r 6
	 * 
	 * */
	private static int getExtra(int digit){
		
		if(incremented == true) return 0; // number incremented but not checked yet whether leading digits are either 3 or 6
		incremented = true;
		
		if(digit <= 2){
			return 3 - digit;
		}else if(digit == 3){
			return 3;
		}else if(digit >=4 && digit <=5){
			return 6 - digit;
		}else{
			return 13 - digit;
		}
	}

	/**
	 * confirms if the giving digit is already valid - 3 or 6.
	 * If not, it returns a number to be added to convert it to next
	 * 3 or 6.
	 * 
	 * */
	private static int confirmValidDigit(int digit){
		
		if(digit <= 3){
			return 3 - digit;
		}else if(digit >=4 && digit <=6){
			return 6 - digit;
		}else{
			return 13 - digit;
		}
	}

	/**
	 * extracts a particular digit from given number e.g. if digitCount is 2,
	 * second digit (ten's digit) is extracted from num
	 * 
	 * */
	private static int extractDigit(int digitCount, int num){
		int quotient = num / (int)Math.pow(10, digitCount -1);
		int remainder = quotient % 10;
		return remainder;
	}
	
	/**
	 * Returns true if number has been processed completly
	 * */
	private static boolean isCompleted(int digitCount, int num){
		int quotient = num / (int)Math.pow(10, digitCount -1);
		return quotient != 0 ? false : true;
	}
	
	/**
	 * Returns number of digits present in a number. 
	 * In other words, length of the number, in string terminology
	 * */
	private static int findNumberOfDigits(int num){
		int countDigit = 0;
		int quotient = -1;
		int digitCount = 2;
		
		while(quotient != 0){
			quotient = num / 10;
			num = quotient;
			digitCount++;
			countDigit++;
		}
		
		return countDigit;
	}

	
	public static void main(String[] args){
		/*int[] arr = {333, 336,956, 999, 800, 858, 99999058, 366};
		for(int num: arr){
			incremented = false;
			System.out.println("num: "+num+", next num: "+findNextNumber(num));
			
			//System.out.println("num: "+num+", next num: "+findNumberOfDigits(num));
		}*/
		
		for(int i = 0; i < 2000; i++){
			//System.out.println("Given num: "+i+", Next num: "+findNextNumber(i));
			assert(findNextNumber(i) == expectedNumber(i));
		}
		System.out.println("done!");
		
	}
	
	/**
	 * Used for testing
	 * */
	public static int expectedNumber(int num){
		
		if(num >= 0 && num <= 2) return 3;
		else if(num >= 3 && num <= 32) return 33;
		else if(num >= 33 && num <= 35) return 36;
		else if(num >= 36 && num <= 62) return 63;
		else if(num >= 36 && num <= 62) return 63;
		else if(num >= 63 && num <= 65) return 66;
		else if(num >= 66 && num <= 332) return 333;
		else if(num >= 333 && num <= 335) return 336;
		else if(num >= 336 && num <= 362) return 363;
		else if(num >= 363 && num <= 365) return 366;
		else if(num >= 366 && num <= 632) return 633;
		else if(num >= 633 && num <= 635) return 636;
		else if(num >= 636 && num <= 662) return 663;
		else if(num >= 663 && num <= 665) return 666;
		else if(num >= 666 && num <= 3332) return 3333;
		
		return -1;
	}
	
}
